package com.ai.zuochengyun.phase01.class01;

import java.util.*;

public class Code15_HeapGreater<T> {

    /**
     * 反向索引表
     */
    private Map<T, Integer> indexMap;

    private List<T> heap;

    private int heapSize;

    private Comparator<? super T> comparator;

    public Code15_HeapGreater(Comparator<T> c) {
        this.comparator = c;
        indexMap = new HashMap<>();
        heap = new ArrayList<>();
        heapSize = 0;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public int size() {
        return heapSize;
    }

    public boolean contains(T t) {
        return indexMap.containsKey(t);
    }

    /**
     * 获取堆顶部的元素
     *
     * @return
     */
    public T peek() {
        return heap.get(0);
    }

    public void push(T t) {
        heap.add(t);
        indexMap.put(t, heapSize);
        heapInsert(heapSize++);
    }

    /**
     * 弹出头部元素
     * @return
     */
    public T pop() {
        T res = heap.get(0);
        // 将头尾位置的元素交换
        swap(0, heapSize - 1);
        // 将尾部的值删掉
        heap.remove(--heapSize);
        indexMap.remove(res);
        // 将头部位置往下沉
        heapify(0);
        return res;
    }

    /**
     * 弹出尾部元素
     * @return
     */
    public T popTail() {
        T res = heap.get(heapSize - 1);
        // 将尾部的值删掉
        heap.remove(--heapSize);
        indexMap.remove(res);
        return res;
    }

    /**
     * 不知道是往上还是往下调整
     *
     * @param t
     */
    public void resign(T t) {
        // 通过对象拿到反向索引表的位置
        int index = indexMap.get(t);
        heapInsert(index);
        heapify(index);
    }

    /**
     * 使用末尾元素替换掉要删除的元素
     *
     * @param t
     */
    public void remove(T t) {
        // 提前获取末尾的元素
        T rep = heap.get(heapSize - 1);
        // 从反向索引表中删除该元素t
        int index = indexMap.get(t);
        indexMap.remove(t);
        // 因为使用末尾元素替换掉要删除的元素，此处将末尾的元素删掉，缩减堆的大小
        // 不用担心末尾的元素会丢失，因为在下面会将其放到要删除元素的位置
        heap.remove(--heapSize);

        // 如果删除的元素不是末尾的元素
        if (t != rep) {
            // 用末尾元素去替换掉要删掉的元素
            heap.set(index, rep);
            indexMap.put(rep, index);
            // 重新调整堆
            resign(rep);
        }
    }

    /**
     * 返回堆上所有的元素
     *
     * @return
     */
    public List<T> getAllElements() {
        return new ArrayList<>(heap);
    }

    /**
     * 向上浮
     *
     * @param index
     */
    public void heapInsert(int index) {
        // 当前元素是否比父节点的元素大，如果是，就上浮
        while (comparator.compare(heap.get(index), heap.get((index - 1) / 2)) > 0) {
            // 交换元素
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public void heapify(int index) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int large = left + 1 < heapSize ? comparator.compare(heap.get(left), heap.get(left + 1)) > 0 ? left : left + 1 : left;
            // 当前节点的值不比子节点中较大的孩子的值小
            if (comparator.compare(heap.get(index), heap.get(large)) >= 0) {
                break;
            }
            // 交换元素
            swap(index, large);
            index = large;
            left = index * 2 + 1;
        }
    }

    private void swap(int i, int j) {
        T temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

}
